package edu.ustb.hash2;

/**
 * @author ShiZhe
 * @create 2020-10-07 21:06
 */
public class HashTable
{
    private DataItem[] hashArray;
    private int arraySize;
    private DataItem nonItem;
    //-------------------------------------------------------------
    HashTable(int size)               // 构造器
    {
        arraySize = size;
        hashArray = new DataItem[arraySize];
        nonItem = new DataItem(-1);
    }
    //-------------------------------------------------------------
    public void displayTable()
    {
        System.out.print("Table: ");
        for(int j=0; j<arraySize; j++)
        {
            if(hashArray[j] != null) {
                System.out.print(hashArray[j].getKey()+ " ");
            } else {
                System.out.print("** ");
            }
        }
        System.out.println("");
    }
    //-------------------------------------------------------------
    public int hashFunc1(int key)
    {
        return key % arraySize;
    }
    //-------------------------------------------------------------
    public int hashFunc2(int key) //再哈希
    {
        return 5 - key % 5;
    }
//-------------------------------------------------------------

    public void insert(int key, DataItem item)
// 假设表未满
    {
        int hashVal = hashFunc1(key);  // 计算哈希值
        int stepSize = hashFunc2(key); // 计算步长

        while(hashArray[hashVal] != null &&
                hashArray[hashVal].getKey() != -1)//非空且数据未删除
        {
            hashVal += stepSize;        // 加步长
            hashVal %= arraySize;       // 循环到表头
        }
        hashArray[hashVal] = item;     // 插入
    }  // end insert()
    //-------------------------------------------------------------
    public DataItem delete(int key)   // 删除
    {
        int hashVal = hashFunc1(key);      //计算哈希值
        int stepSize = hashFunc2(key);     // 计算步长

        while(hashArray[hashVal] != null)  // 非空
        {
            if(hashArray[hashVal].getKey() == key)//找到
            {
                DataItem temp = hashArray[hashVal];
                hashArray[hashVal] = nonItem;
                return temp;
            }
            hashVal += stepSize;
            hashVal %= arraySize;
        }
        return null;                   // 无法找到
    }  // end delete()
    //-------------------------------------------------------------
    public DataItem find(int key)     // 查找
// 假设表未满
    {
        int hashVal = hashFunc1(key);
        int stepSize = hashFunc2(key);

        while(hashArray[hashVal] != null)  // 非空
        {
            if(hashArray[hashVal].getKey() == key) {
                return hashArray[hashVal];   // 找到返回
            }
            hashVal += stepSize;            // 加步长
            hashVal %= arraySize;
        }
        return null;                   // can't find item
    }
//-------------------------------------------------------------
}  // end class HashTable